# 给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
#
#  进阶：你可以在 O(n) 的时间解决这个问题吗？
#
#  示例 1：
# 输入：nums = [3,10,5,25,2,8]
# 输出：28
# 解释：最大运算结果是 5 XOR 25 = 28.
#
#  示例 2：
# 输入：nums = [0]
# 输出：0
#
#  示例 3：
# 输入：nums = [2,4]
# 输出：6
#
#  示例 4：
# 输入：nums = [8,10,2]
# 输出：10
#
#  示例 5：
# 输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
# 输出：127
# 1 <= nums.length <= 2 * 10⁴
# 0 <= nums[i] <= 2³¹ - 1
from typing import List


class Trie:
    def __init__(self):
        self.left = None
        self.right = None


class Solution:
    def findMaximumXOR2(self, nums: List[int]) -> int:
        """
        隐式Trie
        异或性质:如果 a ^ b = c 则 a ^ c = b , b ^ c = a
        一定会有最大的异或结果，设为 max, 则max = nums[i] ^ nums[j](不需要管具体的nums[i]、 nums[j]是多少)

        要使得异或的值大，即要最终结果的高位尽可能的为1(贪心)
        可以从高位到低位依次确定每位是否可为1(贪心)
        :param nums:
        :return:
        """
        res = 0
        mask = 0
        # 1000000, 00000000, 00000000, 00000000
        for i in range(30, -1, -1):
            mask |= (1 << i)
            # print(bin(mask))
            s = set()  # 用于暂存本次所有的前缀(隐式Trie)
            for n in nums:  # 求出当前位所有可能的前缀
                s.add(n & mask)
            # 假设这个数位上是 “1”（贪心策略） ，如果全部前缀尝试完，都不符合条件，这个数位上就是 “0”
            tmp = res | (1 << i)
            for prefix in s:  # 通过前缀判断当前位是否可以为1
                if tmp ^ prefix in s:  # 利用了异或性质:如果 a ^ b = c 则 a ^ c = b , b ^ c = a
                    res = tmp
                    break
        return res

    def findMaximumXOR1(self, nums: List[int]) -> int:
        """
        显式Trie
        用一颗32层的二叉树来存储所有num值，
            将这些值转换成二进制数，从高位开始存储，当前bit为0则为左，1为右
        要得到最大异或值，需要采用贪心策略，从高位开始逐位异或，
            当前bit为0，则需要看有没有右路可以走，
            当前bit为1，则需要看有没有左路可以走，这样才能得到最大的异或值。
        :param nums:
        :return:
        """
        self.trie = Trie()
        res = 0
        for num in nums:
            self.buildTrie(num)
        for num in nums:
            res = max(res, self.search(num))
        return res

    def buildTrie(self, num: int) -> None:
        cur = self.trie
        for i in range(30, -1, -1):
            bit = num & (1 << i)
            # bit = (num >> i) & 1
            if bit:
                if not cur.right:
                    cur.right = Trie()
                cur = cur.right
            else:
                if not cur.left:
                    cur.left = Trie()
                cur = cur.left

    def search(self, num: int) -> int:
        cur = self.trie
        curRes = 0
        for i in range(30, -1, -1):
            bit = (num >> i) & 1
            if not bit and cur.right:
                curRes += 1 << i
                cur = cur.right
            elif bit and cur.left:
                curRes += 1 << i
                cur = cur.left
            elif not cur.right:
                cur = cur.left
            else:
                cur = cur.right
        return curRes

    def findMaximumXOR(self, nums: List[int]) -> int:
        return self.findMaximumXOR2(nums)


if __name__ == "__main__":
    nums = [14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70]
    # num = None
    # if num:
    #     print("xxxx")
    # else:
    #     print("nnnn")
    print(Solution().findMaximumXOR(nums))
